package com.company.math;

/**
 * @author jrue
 * @description https://leetcode-cn.com/problems/sqrtx/
 * @date 2019/11/15 15:37
 * 实现 int sqrt(int x) 函数。
 *
 * 计算并返回 x 的平方根，其中 x 是非负整数。
 *
 * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
 */
public class MySqrt {

    public static void main(String[] args) {
        System.out.println(mySqrt(8));
    }


    public static int mySqrt(int x) {
        if (x == 0) return 0;

        int left = 1,right = x/2;

        while (left < right) {
            int mid = (left + right + 1) >>> 1;

            int p = mid* mid;
            if (p == x) return mid;
            else if ( p < x) {
                left = mid ;
            } else {
                right = mid - 1;
            }

        }
        return left;
    }

}
